import java.util.HashMap;
import java.util.Map;

public class Leetcode1590 {
    public static void main(String[] args) {
        System.out.println(minSubarray(new int[]{3, 1, 4, 2}, 6) == 1);
        System.out.println(minSubarray(new int[]{26, 19, 11, 14, 18, 4, 7, 1, 30, 23, 19, 8, 10, 6, 26, 3}, 26) == 3);
        System.out.println(minSubarray(new int[]{6, 3, 5, 2}, 9) == 2);
        System.out.println(minSubarray(new int[]{1, 1, 1}, 2) == 1);
        System.out.println(minSubarray(new int[]{1, 2, 3}, 7) == -1);
        System.out.println(minSubarray(new int[]{4, 4, 2}, 7) == -1);
        System.out.println(minSubarray(new int[]{8, 32, 31, 18, 34, 20, 21, 13, 1, 27, 23, 22, 11, 15, 30, 4, 2}, 148) == 7);
        System.out.println(minSubarray(new int[]{8, 32, 31, 18, 34, 20, 21, 13, 1, 27, 23, 22, 11, 15, 30, 4, 2}, 148) == 7);
        System.out.println(minSubarray(new int[]{1000000000, 1000000000, 1000000000}, 3) == 0);
        System.out.println(minSubarray(new int[]{1}, 1) == 0);
    }

    //    (a-b) % p = diff
    //    a%p - b%p = diff
    //    a%p - diff = b%p
    //    a%p = diff + b%p

    public static int minSubarray(int[] nums, int p) {
        long sum = 0;
        long[] prefixSum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        if (sum == 0) {
            return 0;
        }

        if (sum < p) {
            return -1;
        }

        long diff = sum % p;

        if (diff == 0) {
            return 0;
        }


        int res = Integer.MAX_VALUE;
        Map<Long, Integer> has = new HashMap<>(nums.length / 2);
        for (int i = 0; i <= nums.length; i++) {
            has.put(prefixSum[i] % p, i);

            long target = (prefixSum[i] - diff + p) % p;
            if (has.containsKey(target)) {
                res = Math.min(res, i - has.get(target));
            }

        }

        return res >= nums.length ? -1 : res;
    }


}
